Embedded systems are increasingly based on multi-core
platforms to cater to increasing performance demands while satisfying power usage constraints. 
Currently, most embedded applications have been successfully deployed and are harnessing the
benefits of their computational capabilities.  However, system designers are unable to leverage the entire potential provided by these platforms to deploy hard real-time applications, for which
upper bounds on worst-case execution times (WCET) must be determined at design time and deadlines must be strictly met at run-time.
Although techniques to determine the WCET of tasks executing on a single core~\cite{wcet-summary} exist,
there are still many open issues in a multi-core setting due to the inherent resource sharing between the cores~\cite{Dasari13SIES}. 
This paradigm of resource sharing does not adhere to the temporal and spatial isolation of components desired by the system designers,
because it creates extra interference between tasks executing asynchronously on different cores, which in-turn further complicates the process of computing the WCETs of the tasks. This problem is important since memory-intensive 
tasks are stalled for a substantial time during data transfers between the cores and the memory. 
Failure to capture this interference at design time results in
non-conservative bounds, while pessimistic analyses may result in a substantial over-estimation of the interference and thereby lead to under-utilizated resources. A particular challenge is that the interference is heavily dependent on the arbitration policy of the memory bus, which covers a diversity of
policies ranging from work-conserving priority-based policies in high-performance soft real-time systems to
non-work-conserving time-division-multiplexing (TDM) for critical systems that require robust partitioning.

Existing work addresses the problem of deriving the upper bounds on bus contention to some extent, but the analysis is
tightly coupled to a particular arbitration policy, such as
TDM~\cite{Rosen07_rtss07,Chatto,Timon,Schra2010,Schra2011} or
non-specified work-conserving arbiters~\cite{Icess11, Ernst}, and a generic framework to handle different arbitration mechanisms does not exist. 
As a result, worst-case execution time estimation tools are limited to
different point solutions for each system under analysis, complicating
implementation and maintenance.
% 
% \todo{It is possible to check with ABSInt if they agree with the
%   above statements and have any supporting references.}

This paper addresses this problem by proposing a general framework for
memory contention analysis that addresses the range of arbitration
policies in multi-core systems and can be implemented in worst-case execution time estimation tools.
The three main contributions of this work are: 
1) A model that captures the best-case and worst-case availability
of the shared memory bus. This model can be applied to a range of arbitration policies in a streamlined manner, and we
demonstrate its flexibility by applying it to two very different cases, being
non-work-conserving TDM and work-conserving fixed-priority arbitration.
2) An algorithm that uses the proposed bus model and leverages the task request-profiles to compute the maximum interference on the bus that a given task can incur.
3) A method to tighten the computed bounds and increase the efficiency and scalability of the
algorithm by splitting the task profile into smaller sampling regions.
%
We experimentally evaluate the proposed approach by
applying it to a multi-core system providing access
to a DRAM via a shared bus. The flexibility of the framework is demonstrated by applying it different arbiters on a set of applications from the WCET test suite~\cite{WCET2010}. We additionally
evaluate the accuracy and the run-time of the analysis for different sample region sizes.
Apart from the proof-of-concept by implementation, we also formally prove the key concepts upon which the algorithm is designed. 
% 
% The rest of this paper is organized as
% follows. Section~\ref{sec:model} presents the system model, followed
% by the problem statement and an overview of our approach in
% Section~\ref{sec:probdef}. The different steps of our approach are
% then discussed in detail, starting with the proposed general bus model
% in Section~\ref{sec:bus_availability}. We then proceed by showing how
% to bound worst-case interference in Sections~\ref{sec:wc_delay}
% and~\ref{sec:wc_assignment}, respectively. This is followed by a method to
% improve the accuracy and reduce run time in
% Section~\ref{sec:complexity_reduction}. The approach is experimentally
% evaluated in Section~\ref{sec:experiments}, before we discuss related
% work in Section~\ref{sec:related_work}. The paper is concluded in
% Section~\ref{sec:conclusion}.

% \todo{It is a problem that we have a four-step approach that maps to
%   three sections with contributions. This means there is not a
%   straight-forward mapping and that it is difficult to explain the
%   difference between Section~\ref{sec:wc_delay}
%   and~\ref{sec:wc_assignment}, since that would require us to discuss
%   the internals of the algorithm already here. Think if it is possible
%   to merge Step 2 and Step 3, or if that section would become too
%   long.}
